/*
 * @lc app=leetcode.cn id=212 lang=cpp
 * @lcpr version=30204
 *
 * [212] 单词搜索 II
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    class TrieNode {
    public:
        bool is_end;
        vector<TrieNode*> children;
        
        TrieNode() : is_end(false), children(26, nullptr) {}
    };

    TrieNode* root;
    vector<pair<int, int>> directions = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1}
    };
    vector<string> res;

    // 插入单词到前缀树
    void insert(string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->is_end = true;
    }

    // 深度优先搜索
    void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, 
        int x, int y, TrieNode* node, string& current) {
        // 越界检查
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visited[x][y]) {
            return;
        }
        
        char c = board[x][y];
        int idx = c - 'a';
        
        // 如果当前字符不在前缀树中，直接返回（剪枝）
        if (!node->children[idx]) {
            return;
        }
        
        // 移动到前缀树的下一个节点
        node = node->children[idx];
        current.push_back(c);
        visited[x][y] = true;
        
        // 如果找到一个完整单词，加入结果集
        if (node->is_end) {
            res.push_back(current);
            node->is_end = false;  // 防止重复添加
        }
        
        // 探索四个方向
        for (auto& dir : directions) {
            dfs(board, visited, x + dir.first, y + dir.second, node, current);
        }
        
        // 回溯
        visited[x][y] = false;
        current.pop_back();
    }

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        // 初始化前缀树
        root = new TrieNode();
        for (string& word : words) {
            insert(word);
        }
        
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        string current;
        
        // 从每个单元格开始搜索
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dfs(board, visited, i, j, root, current);
            }
        }
        
        return res;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]\n["oath","pea","eat","rain"]\n
// @lcpr case=end

// @lcpr case=start
// [["a","b"],["c","d"]]\n["abcb"]\n
// @lcpr case=end

 */

